/*
 * Author: Wang Hsutung
 * Date: 2015/11/15
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */
#include <iostream>
#include <string>
#include <stack>
#include <deque>
#include <cassert>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int c, TreeNode *l = NULL, TreeNode *r = NULL) :
        val(c), left(l), right(r) {}

    static void print(TreeNode *p, string prefix = "")
    {
        if (!p) {
            cout << "(null)" << endl;
            return;
        }
        cout << p->val << endl;

        if (p->left || p->right) {
            cout << prefix << "├── ";
            print(p->left,  prefix + "│   ");
            cout << prefix << "└── ";
            print(p->right, prefix + "    ");
        }
    }
};

struct BinTree {
    TreeNode *root;

    BinTree() : root(NULL) {}

    void print(void)
    {
        TreeNode::print(root);
    }

    void levelOrderTraverse(void)
    {
        if (root == NULL)
            return;

        std::stack<TreeNode*> nodeStack;
        std::stack<bool>  statStack; /* Whether a node is visited */
        nodeStack.push(root);
        statStack.push(0);

        while (!nodeStack.empty()) {
            TreeNode *p = nodeStack.top();
            nodeStack.pop();
            bool visited = statStack.top();
            statStack.pop();

            if (visited) {
                cout << p->val << " ";
                continue;
            }

            if (p->right != NULL) {
                nodeStack.push(p->right);
                statStack.push(false);
            }
            nodeStack.push(p);
            statStack.push(true);
            if (p->left != NULL) {
                nodeStack.push(p->left);
                statStack.push(false);
            }
        }
        cout << endl;
    }
};

struct Forest{
    BinTree trees;

    static void mergeTree(TreeNode *root)
    {
        if (root != NULL) {
            mergeTree(root->left);
            mergeTree(root->right);
            if (root->left != NULL) {
                assert(root->left->right == NULL);
                root->left->right = root->right;
            } else {
                root->left = root->right;
            }
            root->right = NULL;
        }
    }

    void append(BinTree bt)
    {
        mergeTree(bt.root);
        bt.root->right = this->trees.root;
        trees = bt;
    }

    void print() {
        trees.print();
    }

    void levelOrderTraverse()
    {
        deque<TreeNode*> que;
        if (trees.root != NULL)
            que.push_back(trees.root);

        while (!que.empty()) {
            TreeNode *p = que.front();
            que.pop_front();
            while (p != NULL) {
                if (p->left != NULL) // 令子节点(left Child)入队
                    que.push_back(p->left);
                cout << p->val << " ";
                p = p->right; // 跳转到右兄弟
            }
        }
    }
};

int main(void)
{
    BinTree tree1, tree2, tree3;
    tree1.root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
    tree2.root = new TreeNode(4, new TreeNode(5, NULL, new TreeNode(7)), new TreeNode(6));
    tree3.root = new TreeNode(8, new TreeNode(9));

    cout << "***** 有以下三棵树 *****\n";
    cout << "------【1号树】------\n";
    tree1.print();
    cout << "------【2号树】------\n";
    tree2.print();
    cout << "------【3号树】------\n";
    tree3.print();

    Forest fst;
    fst.append(tree3);
    fst.append(tree2);
    fst.append(tree1);
    cout << "\n按 “左孩子、右兄弟” 法则构造得到森林如下: \n";
    fst.print();
    cout << "其层序遍历(按森林中树的层次从上到下、从左到右)为: ";
    fst.levelOrderTraverse();
    cout << endl;
    return 0;
}
